package lc2;
import java.util.*;
import org.junit.*;

public class Ex1438 {
    class Solution {
        public int longestSubarray(int[] nums, int limit) {
            int res = 1;
            int lo = 0, hi = 0;
            int n = nums.length;

            Deque<Integer> min = new ArrayDeque<Integer>();
            Deque<Integer> max = new ArrayDeque<Integer>();

            while (hi < n) {
                while (hi < n) {

                    while (!min.isEmpty() && nums[min.peekLast()] >= nums[hi]) {
                        min.pollLast();
                    }
                    while (!max.isEmpty() && nums[max.peekLast()] <= nums[hi]) {
                        max.pollLast();
                    }
                    min.offer(hi);
                    max.offer(hi);

                    int d = nums[max.peekFirst()] - nums[min.peekFirst()];
                    if (d > limit) {
                        break;
                    }

                    hi++;
                }

                res = Math.max(res, hi - lo);

                //移动左指针，进行下一轮试探
                while (lo < hi) {
                    int maxL = max.peekFirst(), minL = min.peekFirst();
                    if (nums[maxL] - nums[minL] <= limit) {
                        break;
                    }
                    if (minL < maxL) {
                        min.pollFirst();
                        lo = minL + 1;
                    } else {
                        max.pollFirst();
                        lo = maxL + 1;
                    }
                }
            }

            return res;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{8,2,4,7};
        System.out.println(s.longestSubarray(nums, 4));
    }
}
